TSATOA

게임 개발 노트
알고리즘 공부
- 문제풀이(Problem Solving)
  - 1. 입문문제
- 알고리즘(Algorithm)
알아두면 좋은 지식
- Github 블로그 만들기
정보처리기사
- 1. 요구사항 확인1
취업 준비
- LG WayFit 인적성
CS 전공 복습
Lg Aimers
Home

Contact

Home > 알고리즘 공부 > 문제풀이(Problem Solving)

Now Loading ...

문제풀이(Problem Solving)

입문 문제 - 프로그래머스
잡담 방학을 시작한지 벌써 보름이 지났다. 계획은 열심히 세웠는데…잘 실행되고 있지는 않은 것 같다. LG Aimer 공부, 정처기 실기 공부, 코테 공부, 프로젝트, 영어 공부 등등 할게 너무 많다. 거기에 이사 준비도 해야하고…놀기도 해야한다~!~!! 먼저 코딩테스트 준비를 하려고 보니, 오랜만에 C++을 사용했다고 너무 어색했다. C++에 익숙해질 필요가 있었다. 간단하게 프로그래머스 입문 100제를 풀어 손에 익히고, 부족한건 다시 살펴보며 적응했다. 중간중간 친구 생일, 이사 문제 등이 겹쳐 생각보다 오래 걸렸다… 2~3일이면 다 풀 줄 알았는데 일주일이나 걸렸다. 푸는데는 딱히 어려움은 없었다. 이번 포스트에서는 100 문제를 풀면서 꼭 알아야 하거나 새롭게 알게 된 내용을 정리할 것이다. 프로그래머스 입문 문제 문제 풀면서 C++ 사용 시 꼭 알아야 하는 것, 알아두면 좋은 것을 정리하니 15문제 정도가 나왔다. 각각 문제에 대해 알아보자. 10 중앙값 구하기 sort를 사용했다. algorithm 헤더파일을 추가해야 한다. 함수 인자로는 이터레이터를 지원하는 컨테이너의 시작과 끝이 입력된다. 컨테이너란 데이터를 저장하고 관리하기 위한 클래스를 말한다.(array, vector, list, map, deque 등..) sort는 C++ STL에서 제공하는 함수로, nlogn의 시간복잡도를 보장하는 오름차순 정렬 함수이다. 인자에 비교 함수를 추가해 오름차순 뿐만아니라 다른 기준으로 정렬도 되지만, 이건 나중에 알아보자. #include<algorithm> sort(a.begin(),a.end()); 13 피자 나눠 먹기(1) ceil를 사용했다. cmath 헤더파일을 추가해야 한다. 무조건 소수점 자리를 올림한다. #include<cmath> ceil(Z); 14 피자 나눠 먹기(2) __gcd를 사용했다. algorithm 헤더파일을 추가해야 한다. 두 수의 최대공약수를 구하는 함수이다. #include<algorithm> __gcd(a,b); 20 배열 뒤집기 vector를 순회할 때는 여러 방법이 있다. 인덱스를 통해 접근할 수 있고, iterator를 통해서 접근할 수도 있다. 인덱스를 통한 접근법 for(int i=0;i<vec.size();i++) answer.push_back(vec[i]); iterator를 통한 접근법 for(vector<int>::iterator i=vec.begin();i<vec.end();i++) answer.push_back(*i); 21 문자열 뒤집기 reverse를 사용했다. algorithm 헤더파일을 추가해야 한다. 함수 인자로는 이터레이터를 지원하는 컨테이너의 시작과 끝이 입력된다. 해당 원소를 거꾸로 뒤집는다. #include<algorithm> reverse(a.begin(),a.end()); 25 특정 문자 제거하기 find를 사용하여 string에서 특정 문자의 존재 유무를 찾을 수 있다. 찾고자 하는 문자가 존재한다면 해당 문자의 위치를 반환하고, 존재하지 않다면 string::npos를 반환한다. find 호출 주체와, 찾고자 하는 문자열 모두 string type이어야 한다. #include<string> if(a.find(b)!=string::npos) ~~~; 추가로 algorithm에서도 find가 있다. 범위 내 원소들 중에서 value와 일치하는 첫번째 원소의 iterator를 반환한다. 일치하는 원소가 없을 경우 마지막 iterator를 반환한다. #include<algorithm> find(vec.begin(), vec.end(), a); //실패 시 vec.end() 반환 34 모스부호(1) unordered_map은 키-값 쌍의 데이터를 저장하는 해시 테이블 기반의 맵이다. 중복된 키값을 가질 수 없으며, 순서를 보장하지 않는다. 해시 테이블을 사용해 상수의 시간복잡도로 빠른 검색, 삽입, 삭제 등이 가능하다. first,second를 통해 key와 value에 접근할 수 있다. #include<unordered_map> unordered_map<int,char> umap {% raw %}{{1,'a'},{2,'b'}}{% endraw %}; umap.find(1)->second //a istringstream을 사용해서 string을 특정 문자 기준으로 분리할 수 있다. sstream 헤더파일을 추가해야 한다. #include<string> #include<sstream> istringstream str(letter); string word; while(getline(str,word,' ')){ a.push_back(word); } 38 2차원으로 만들기 2차원 vector의 경우 열 index를 넣기 전 행 index를 추가해 주어야 한다. #include<vector> vector<vector<int>> vec; vec.push_back(vector<int>()); vec[0].push_back(123); 44 팩토리얼 함수 선언과 호출은 아래처럼 C와 동일하다. int factorial(int n){ if(n<=1) return 1; return n*factorial(n-1); } factorial(n); 49 컨트롤 제트 compare을 통해 두 string 문자열을 비교할 수 있다. 두 문자열이 같으면 0을 반환하고, 다르면 -1을 반환한다. #include<string> #include<iostream> if(a.compare(b)==0) cout << "같은 문자" <<endl; 57 영어가 싫어요 나도다…나도 영어가 싫다… substr을 통해 string 문자열을 일부 추출할 수 있다. 추출을 시작할 위치와 추출할 크기를 인자로 받는다. erase를 통해 문자열을 삭제할 수도 있다. 삭제할 문자열의 시작 위치와 크기를 인자로 받는다. #include<string> a.substr(0,3); a.erase(0,2); 문자에서 숫자, 숫자에서 문자로 변경이 필요할 때가 있다. stoi, stol, atoi 등을 통해 문자열을 int, long 등으로 변환하거나 char 문자를 int로 변환할 수 있다. 또한 to_string을 통해 정수를 문자열로 변환할 수도 있다. strnum = to_string(num); num = stoi(strnum); 58 인덱스 바꾸기 swap을 통해 두 값을 바꿀 수 있다. swap(str1[0],str1[3]); 82 안전지대 C++에서 함수 호출 방법으로는 크게 call by reference와 call by value가 있다. call by value의 경우 인자 값이 매개변수에 복사되어, 매개변수에 조작을 가해도 인자에 영향을 안준다. 44 팩토리얼 문제처럼 선언하고 호출한다.(C와 동일) call by reference의 경우 인자 값이 매개변수로 복사되는 것은 동일하지만, 주소 값이 복사되어 매개변수 조작 시 인자에도 영향을 준다. C++에서는 C와는 다르게 참조변수가 추가되어, 매개변수를 참조변수로 선언 가능하다. void swap1(vector<vector<int>> &a,int i, int j){ int tmp; tmp = a[i][j]; a[i][j] = a[j][i]; a[j][i] = tmp } swap1(a,2,3); 90 등수 매기기 10 중앙값 구하기에서 sort를 사용하여 정렬했었다. 이때 오름차순으로 정렬되었었는데, 내림차순으로는 어떻게 정렬할까? sort함수의 3번째 인자로 사용자 정의 함수를 넣으면 된다. #include<algorithm> bool compare(double a, double b){ return a>b; } sort(a.begin(),a.end(),compare); 94 이진수 더하기 문자열의 마지막에 삽입은 push_back 또는 +=으로 추가할 수 있다. push_back의 경우 char type만 삽입할 수 있으며, +=은 string type을 추가할 수 있다. 문자열의 특정 위치 삽입은 insert를 통해 이루어진다. 삽입하고자 하는 위치와 문자열을 인자로 받는다. #include<string> a.insert(0,b); 마무리 코딩테스트 공부 첫 시작으로 100문제 푸는건 좋은 선택이었다. 문제를 풀면서 정리하다 보니 생각보다 기본기가 많이 부족했다는 것을 알게 되었다. 따로 필수 문법과 알고리즘을 정리해 봐야겠다. 추가로 책도 사서 한번 봐야겠다. 프로그래머스에서 책 코딩 테스트 합격자 되기 c++편이 올해 5월에 나왔다. 구성을 살펴보니 알고리즘 효율 분석, 필수 문법, 배열, 스택, 큐, 해시, 트리, 집합, 그래프, 백트래킹, 정렬, 시뮬레이션, DP, 그리디 등 내가 원하는 내용이 모두 들어있다. 거기에 프로그래머스 문제 기준 설명이 되어있기 때문에 더더욱 마음에 들었다. 앞으로 이 책을 사서 문법과 알고리즘을 정리하고, 문제들을 풀어봐야겠다~!~!!
알고리즘 공부 · 2024-07-09

Touch background to close